#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2019/5/13 10:52
# @USER    : 717-3
# @File    : LongestPalindromicSubsting.py
# @Software: PyCharm
# @Version  : Python-3.6
# @TASK:

"""
- Two Pointers
- String
- Dynamic Programming
"""


class Solution:
    """
    Given a string s, find the longest palindromic substring in s.
    You may assume that the maximum length of s is 1000.

    :param s:string
    :return:the longest palindromic substring

    Example 1:
        Input: "babad"

        Output: "bab"

        Note: "aba" is also a valid answer.
    Example 2:
        Input: "cbbd"

        Output: "bb"
    """

    def longestPalindrome(self, s: str) -> str:

        if len(s) > 1:
            flag = len(s)
            while flag:
                for i in range(len(s) + 1 - flag):
                    string = s[i:flag + i]
                    if string == string[::-1]:
                        return string
                flag = flag - 1
        else:
            return s

    def longestPalindrome_ai(self, s: str) -> str:
        """
        - 负责遍历每个可能的中心点，并检查奇数和偶数长度的回文子串。通过调用expand方法获取当前中心的最长回文子串，并更新记录的最长子串。
        - expand方法：该方法从给定的左右指针开始，向两边扩展，直到不再满足回文条件。返回找到的回文子串。
        - 这种方法的时间复杂度为O(n^2)，其中n是字符串的长度。每个字符作为中心点向两边扩展最多需要O(n)的时间，而共有n个字符，因此总的时间复杂度为O(n^2)。空间复杂度为O(1)，因为我们只需要常数空间来存储结果。
        """
        if len(s) < 1:
            return ""
        max_str = s[0]
        for i in range(len(s)):
            # 奇数长度的回文
            odd = self.expand(s, i, i)
            # 偶数长度的回文
            even = self.expand(s, i, i + 1)
            # 更新最长回文
            if len(odd) > len(max_str):
                max_str = odd
            if len(even) > len(max_str):
                max_str = even
        return max_str

    def expand(self, s, l, r):
        # 从中心向两边扩展，直到不再满足回文条件
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1
            r += 1
        # 返回当前找到的回文子串
        return s[l + 1:r]

    def longestPalindrome_dp(self, s: str) -> str:
        """
        - 动态规划转移方程：子串s[i...j]是回文的条件是s[i] == s[j]且子串s[i+1...j-1]是回文。
        - 顺序处理：按子串长度递增的顺序处理，确保在计算dp[i][j]时，其依赖的中间子串dp[i+1][j-1]已被计算。
        - 复杂度分析：时间复杂度为O(n²)，空间复杂度为O(n²)，适用于中等长度的字符串。
        """
        n = len(s)
        dp = [[False] * n for _ in range(n)]
        ans = [0, 0]  # 初始化为第一个字符

        # 所有单个字符都是回文
        for i in range(n):
            dp[i][i] = True

        # 检查长度为2的子串
        for i in range(n - 1):
            if s[i] == s[i + 1]:
                dp[i][i + 1] = True
                ans = [i, i + 1]

        # 检查长度大于等于3的子串
        for diff in range(2, n):
            for i in range(n - diff):
                j = i + diff
                if s[i] == s[j] and dp[i + 1][j - 1]:
                    dp[i][j] = True
                    # 更新最长回文的起止位置
                    ans = [i, j]

        i, j = ans
        return s[i: j + 1]


if __name__ == '__main__':
    S = Solution()
    # Q5
    sample = 'babad'
    # sample = 'cbbdbbc'
    print(S.longestPalindrome(sample))
    print(S.longestPalindrome_ai(sample))
    print(S.longestPalindrome_dp(sample))
    print('done')
